# -*- coding: utf-8 -*-
# @Time: 2021/11/9 14:59
# @Author: lijinxi
# @File    : k_short_path.py
# @desc
import ksp

from service_placement import *

# K条最短路劲的朴素算法
Y = []


def find_valid_path(strategy1, strategy2, start_node, end_node, num_path):
    valid_path = list()
    graph = ksp.AdjacencyDict(strategy1)
    path_one = ksp.yen(graph, start_node, end_node, num_path)
    graph = ksp.AdjacencyDict(strategy2)
    path_two = ksp.yen(graph, end_node, start_node, num_path)
    for x in path_one:
        x = x['path']
        for y in path_two:
            flag = True
            for node in y['path'][1:-1]:
                if node in x:
                    flag = False
            if flag:
                x.extend(y['path'][1:])
                if len(x) > 2 and x not in valid_path:
                    valid_path.append(x)
    return valid_path


def cal_availability(primary_availability, backup_availability):
    val = 1
    for i in range(len(primary_availability)):
        val *= 1 - (1 - primary_availability[i]) * (1 - backup_availability[i])
    return val
    # 更新资源剩余量


class KShortPath(object):
    def __init__(self, number_edge_servers=25, rows=5, cols=5):
        self.rows, self.cols = rows, cols  # 5*5的网格矩阵
        self.nodes = [chr(ord('A') + i) for i in range(number_edge_servers)]
        self.number_edge_servers = number_edge_servers

        # 邻接点
        self.left_up_nodes = dict()
        self.left_down_nodes = dict()
        self.right_up_nodes = dict()
        self.right_down_nodes = dict()

    def valid(self, x, y):  # 点在网格内
        if 0 <= x < self.rows and 0 <= y < self.cols:
            return True
        else:
            return False

    # 向左和上走
    def x_left_y_up(self, x, y):
        valid_nodes = []
        if self.valid(x - 1, y):
            valid_nodes.append(self.cols * y + x - 1)
        if self.valid(x, y - 1):
            valid_nodes.append((y - 1) * self.cols + x)
        return valid_nodes

    # 向左和向下
    def x_left_y_down(self, x, y):
        valid_nodes = []
        if self.valid(x - 1, y):
            valid_nodes.append(x - 1 + self.cols * y)
        if self.valid(x, y + 1):
            valid_nodes.append(self.cols * (y + 1) + x)
        return valid_nodes

    # 向右和向上
    def x_right_y_up(self, x, y):
        valid_nodes = []
        if self.valid(x, y - 1):
            valid_nodes.append(self.cols * (y - 1) + x)
        if self.valid(x + 1, y):
            valid_nodes.append(self.cols * y + x + 1)
        return valid_nodes

    # 向右和向下
    def x_right_y_down(self, x, y):
        valid_nodes = []
        if self.valid(x, y + 1):
            valid_nodes.append(self.cols * (y + 1) + x)
        if self.valid(x + 1, y):
            valid_nodes.append(self.cols * y + x + 1)
        return valid_nodes

    # 生成邻解点数组
    def generate_adjacent_nodes(self):
        for i in range(self.number_edge_servers):
            _a = dict()
            y, x = i // self.cols, i % self.cols

            for j in self.x_left_y_up(x, y):
                _a[self.nodes[j]] = 1
            self.left_up_nodes[self.nodes[i]] = _a

            _a = dict()
            for j in self.x_left_y_down(x, y):
                _a[self.nodes[j]] = 1
            self.left_down_nodes[self.nodes[i]] = _a

            _a = dict()
            for j in self.x_right_y_up(x, y):
                _a[self.nodes[j]] = 1
            self.right_up_nodes[self.nodes[i]] = _a

            _a = dict()
            for j in self.x_right_y_down(x, y):
                _a[self.nodes[j]] = 1
            self.right_down_nodes[self.nodes[i]] = _a

    # 在无向图上生成无环最短路径
    def generate_k_shortest_path(self, start_node, num_path=20):
        valid_path = list()
        for end_node in self.nodes:
            if end_node == start_node:
                continue
            for i in find_valid_path(self.left_up_nodes, self.right_down_nodes, start_node, end_node, num_path):
                if i not in valid_path:
                    valid_path.append(i)
            # for i in find_valid_path(self.left_up_nodes, self.right_down_nodes, end_node, start_node, num_path):
            #     if i not in valid_path:
            #         valid_path.append(i)
            for i in find_valid_path(self.left_down_nodes, self.right_up_nodes, start_node, end_node, num_path):
                if i not in valid_path:
                    valid_path.append(i)
            # for i in find_valid_path(self.left_down_nodes, self.right_up_nodes, end_node, start_node, num_path):
            #     if i not in valid_path:
            #         valid_path.append(i)
        return valid_path

    def algorithm(self, K=3, ratio=1.0):
        backup_num = 0
        acceptance = 0
        _sp = ServicePlacement(number_requests=1600)
        _sp.initialize_requests(ratio=ratio)
        self.generate_adjacent_nodes()
        t = time.time()
        for i in range(_sp.number_requests):
            node_index = i // (int(_sp.number_requests / _sp.number_edge_servers))
            valid_path = self.generate_k_shortest_path(self.nodes[node_index])
            length = _sp.network_function_matrix[i].sum()
            count = 0
            k_path = []
            for j in valid_path:  # 取前K条可用路径
                if count == K:
                    break
                if len(j) > length:
                    k_path.append(j)
                    count += 1
            # 放置主VNF的资源
            functions_index = []  # 此SFC具有的网络功能
            primary_availability = []  # 一起考虑的可用性
            primary_nodes = []
            for k in range(_sp.type_network_functions):
                if _sp.network_function_matrix[i][k] == 1:
                    functions_index.append(k)  # 保存索引

            for path in k_path:  # 找到可用路径
                k = 0
                primary_availability.clear()
                primary_nodes.clear()
                for node in path[:-1]:
                    index = ord(node) - ord('A')
                    if k < length and _sp.node_computing_capacity[index] >= \
                            _sp.computing_capacity_vector[functions_index[k]]:
                        # 找到可放置的节点
                        primary_availability.append(
                            _sp.node_availability_vector[index] * _sp.function_availability_vector[functions_index[k]])
                        k += 1
                        primary_nodes.append(index)
                if k == length:
                    break

            # 放置备份的节点
            backup_nodes = []
            if len(primary_availability) == length:  # 所有的主VNF被合理放置
                # 计算可用性
                # print(primary_nodes, primary_availability)
                backup_availability = np.zeros(shape=(length,), dtype=np.float64)
                k = 0
                for node in self.nodes:
                    if cal_availability(primary_availability, backup_availability) <= _sp.availability_vector[i]:
                        index = ord(node) - ord('A')
                        if _sp.node_computing_capacity[index] >= _sp.computing_capacity_vector[functions_index[k]]:
                            backup_nodes.append(index)
                            backup_availability[k] = \
                                _sp.node_availability_vector[index] * _sp.function_availability_vector[
                                    functions_index[k]]
                            k += 1
                        if k == length:
                            break
                # print(backup_nodes, backup_availability)
                if cal_availability(primary_availability, backup_availability) >= _sp.availability_vector[i]:
                    # 减去所有资源
                    for n in range(length):
                        _sp.node_computing_capacity[primary_nodes[n]] -= _sp.computing_capacity_vector[
                            functions_index[n]]
                        if n < len(backup_nodes):
                            _sp.node_computing_capacity[backup_nodes[n]] -= _sp.computing_capacity_vector[
                                functions_index[n]]
                    # TODO:时间约束
                    acceptance += 1
                    backup_num += len(backup_nodes)

        print(acceptance, backup_num)
        print("time:", time.time() - t)
        Y.append(acceptance)


def method_computation():
    for i in range(0, 201, 10):
        k_s = KShortPath()
        k_s.algorithm(K=3, ratio=i / 100)
    print(Y)


if __name__ == '__main__':
    # method_computation()
    k_s = KShortPath()
    k_s.algorithm(K=3)
